{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "python实现，遍历所有数据点，找出$n$个距离最近的点的分类情况，少数服从多数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "import math\n",
    "\n",
    "import sklearn.datasets as datasets\n",
    "from sklearn.model_selection import train_test_split\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 实验参数：选择不同的数据集\n",
    "#dataset = datasets.load_iris()\n",
    "dataset = datasets.load_wine()\n",
    "#dataset = datasets.load_breast_cancer()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "======================= dataset information =======================\n",
      "Total sample number: 89, Feature dimension: 13, Category number: 3\n",
      "category 2 has 24 samples\n",
      "category 1 has 30 samples\n",
      "category 0 has 35 samples\n",
      "Training sample number: 71, Test sample number: 18\n"
     ]
    }
   ],
   "source": [
    "# 实验参数：选择不同的数据规模\n",
    "sample_rate = 0.5 # 采样率（可以选择小于1）\n",
    "assert sample_rate>0 and sample_rate<=1\n",
    "nSample = math.floor(dataset.data.shape[0]*sample_rate)\n",
    "idx = random.sample(range(dataset.data.shape[0]), nSample)\n",
    "\n",
    "X = dataset.data[idx][:]\n",
    "y = dataset.target[idx][:]\n",
    "y_stat = Counter(y)\n",
    "print('======================= dataset information =======================')\n",
    "print('Total sample number: %d, Feature dimension: %d, Category number: %d' % (X.shape[0], X.shape[1], len(y_stat)))\n",
    "for category in y_stat:\n",
    "    print('category %d has %d samples' % (category, y_stat[category]))\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)\n",
    "print('Training sample number: %d, Test sample number: %d' % (X_train.shape[0], X_test.shape[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#KNN类定义\n",
    "class KNN:\n",
    "    def __init__(self, X_train, y_train, n_neighbors=3, p=2): # 通过n_neighbors修改k值\n",
    "        \"\"\"\n",
    "        parameter: n_neighbors 临近点个数\n",
    "        parameter: p 距离度量\n",
    "        \"\"\"\n",
    "        self.n = n_neighbors\n",
    "        self.p = p\n",
    "        self.X_train = X_train\n",
    "        self.y_train = y_train\n",
    "\n",
    "    def predict(self, X):\n",
    "        # 取出n个点\n",
    "        knn_list = []\n",
    "        for i in range(self.n):\n",
    "            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)\n",
    "            knn_list.append((dist, self.y_train[i]))\n",
    "\n",
    "        for i in range(self.n, len(self.X_train)):\n",
    "            max_index = knn_list.index(max(knn_list, key=lambda x: x[0]))\n",
    "            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)\n",
    "            if knn_list[max_index][0] > dist:\n",
    "                knn_list[max_index] = (dist, self.y_train[i])\n",
    "\n",
    "        # 统计\n",
    "        knn = [k[-1] for k in knn_list]\n",
    "        count_pairs = Counter(knn)\n",
    "#         max_count = sorted(count_pairs, key=lambda x: x)[-1]\n",
    "        max_count = sorted(count_pairs.items(), key=lambda x: x[1])[-1][0]\n",
    "        return max_count\n",
    "\n",
    "    def score(self, X_test, y_test):\n",
    "        right_count = 0\n",
    "        n = 10\n",
    "        for X, y in zip(X_test, y_test):\n",
    "            label = self.predict(X)\n",
    "            if label == y:\n",
    "                right_count += 1\n",
    "        return right_count / len(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "precision rate: 66.67%\n"
     ]
    }
   ],
   "source": [
    "# 实验参数：选择不同的K值\n",
    "K=3\n",
    "assert K<=X_train.shape[0]\n",
    "clf = KNN(X_train, y_train, K)\n",
    "print('precision rate: {:.2%}'.format(clf.score(X_test, y_test)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test Point category: 2\n"
     ]
    }
   ],
   "source": [
    "# 实验参数：选择不同的测试样本\n",
    "test_idx = 0\n",
    "assert test_idx<X_test.shape[0]\n",
    "test_point = X_test[0]\n",
    "print('Test Point category: {}'.format(clf.predict(test_point)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
